APPLYING MULTIHEURISTIC APPROACH O RANDOMLY GENERATING GRAPHS WITH A GIVEN DEGREE SEQUENCE

Mel'nikov Boris Feliksovich, Doctor of physical and mathematical sciences, professor, sub-department of applied mathematics and informatics, Togliatti State University (14 Belorusskaya street, Togliatti, Russia), B.Melnikov@tltsu.ru
Sayfullina Elena Faridovna, Postgraduate student, Togliatti State University (14 Belorusskaya street, Togliatti, Russia), elena-fairy@yandex.ru

519.171, 519.178

Background. Graphs with a given degree sequence are often regarded as models for many complex tasks. This makes it necessary to study algorithms for generating graphs with a given degree sequence. The purpose of this study is to review the existing methods and to develop our own algorithm for generating a graph with a given degree sequence. The authors give the definition of a graphic sequence, as well as the criteria to check whether a given sequence is graphic or not.
Results. The paper presents the algorithm developed by the authors which is based on one of the screening criteria of the multiheuristic approach (the branch and bound method). The paper also presents the notion of the second-order degree sequence and the modification of the developed algorithm for generating random graphs with a given second-order degree sequence. This modification is also based on the branch and bound method. Thus, a new approach to the generation of random graphs has been proposed. In the computational experiments based on some distribution functions the sequence of a given size (the predicted number of graph nodes) was generated. If the generated sequence is graphical, the graph can be generated on its basis. Then, an-other graph based on second-order degree sequence was generated. The average execution time (in milliseconds) within the different distribution functions and different dimensions of the graph was stated.
Conclusions. These different options for generating random graphs can be useful in many applications, especially in network models, the most important of them being mathematical models of the Internet and social networks, as well as artificial neural networks. Another possible direction for continuation of the research described in this paper is a "tuning" of specific algorithms for solving discrete optimization problems (e.g. the problem of testing isomorphism in specific areas of the graph application).

algorithms for generating random graphs, a degree vector and and its generalizations, graphic sequence, the branch and bound method.

1. Kharari F. Teoriya grafov [Graph theory]. Moscow: Mir, 1973, 302 p.
2. Raygorodskiy A. Kvant [Quantum]. 2012, no. 4, pp. 12–16.
3. Ostroumova L. Trudy Moskovskogo fiziko-tekhnicheskogo instituta [Proceedings of Moscow Institute of Physics and Technology]. 2012, vol. 4, no. 1 (13), pp. 29–40.
4. Breer V. Upravlenie bol'shimi sistemami [Grand system control]. 2009, no. 27, pp. 169–204.
5. Available at: http://www.p2p13.org/ (data obrashcheniya: 16.06.2013).
6. Erdös P., Miklós I., Toroczkai Z. Electr. J. Comb. 2010, vol. 17, no. 1.
7. Bollobás B. Random Graphs. Cambridge: Cambridge Univ. Press, 2001.
8. Bollobás B., Riordan O. Handbook of graphs and networks. Weinheim: Wiley-VCH, 2003, pp. 1–34.
9. Mel'nikov B., Pivneva S., Rogova O. Stokhasticheskaya optimizatsiya v informatike [Stochastic optimization in computer science]. 2010, no. 6, pp. 74–82.
10. Melnikov B. Proc. of the Eighth International Conference on High-Performance Computing in Asia-Pacific Region, IEEE Computer Society. Washington, 2005, pp. 73–80.
11. Mel'nikov B. Kibernetika i sistemnyy analiz (NAN Ukrainy) [Cybernatics and system analysis (National Academy of Sciences of Ukraine)]. 2006, no. 3, pp. 32–42.
12. Iványi. A. Acta Universitatis Sapientiae, Informatica. 2009, vol. 1, no. 1, pp. 71−88.
13. Frank H., Hakimi S. IEEE Transactions on. 1965, vol. 12, no. 3, pp. 44–51.
14. Mel'nikov B., Mel'nikova E. Izvestiya vysshikh uchebnykh zavedeniy. Povolzhskiy region. Estestvennye nauki [University proceedings. Volga region. Natural sciences]. 2007, no. 6, pp. 3–11.
15. Melnikov B., Tsyganov A. 5th Int. Symp. on Parallel Architectures, Algorithms and Programming, IEEE Computer Society Ed. Taipei, 2012, pp. 194–201.
16. Gudman S., Khidetniemi S. Vvedenie v razrabotku i analiz algoritmov [Introduction into algorithm design and analysis]. Moscow: Mir, 1981, 368 p.
17. Gromkovich Yu. Teoreticheskaya informatika. Vvedenie v teoriyu avtomatov, teoriyu vychislimosti, teoriyu slozhnosti, teoriyu algoritmov, randomizatsiyu, teoriyu svyazi i kriptografiyu [Theoretical computer sciences. Introduction into automata theory, theory of calculability, complexity theory, algorithm theory, randomization, communication and cryptography theory]. Saint Petersburg: BKhV-Peterburg, 2010.
18. Berg B. Markov Chain Monte Carlo Simulations and Their Statistical Analysis. Singa-pore, World Scientific Publ., 2004, 361 p.
19. Steger A., Wormald N. Combinatorics, Probab. and Comput. 1999, no. 8, pp. 377–396.
20. Rogova O. Podkhod k otsenke reprezentativnosti sluchayno sgenerirovannykh diskretnykh struktur na primere nedeterminirovannykh konechnykh avtomatov: dis. kand. fiz.-mat. nauk [Approach to estimation of randomly generated discrete structure representativeness by the example of nondeterministic finite automata: dissertation to apply for the degree of the candidate of physical and mathematical sciences]. Tol'yatti: TGU, 2012.
21. Mel'nikova E., Sayfullina E. Problemy informatiki v obrazovanii, upravlenii, ekonomike i tekhnike: tr. XII Mezhdunar. nauchnotekhn. konf. [Problems of computer science in education, administration, economy and technology: proceedings of XII International scientific technological conference]. Penza: Privolzhskiy Dom znaniy, 2012, pp. 40–42.
22. Mel'nikov B. Vestnik Mosk. un-ta. Ceriya. Vychisl. matem. i kib-ka [Bulletin of Moscow University. Series. Calculus mathematics and cybernetics]. 1996, no. 4, pp. 49–54.